#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    int massage(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        vector<int> fp(len);
        vector<int> gp(len);
        fp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            fp[i] = gp[i - 1] + nums[i];
            gp[i] = max(fp[i - 1], gp[i - 1]);
        }
        return max(fp[len - 1], gp[len - 1]);
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        vector<int> f(len);
        vector<int> g(len);
        f[0] = nums[0];
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i < len; i++) {
            f[i] = g[i - 1] + nums[i];
            if (i != 1) g[i] = max(f[i - 1], g[i - 1]);
        }
        ans1 = max(f[len - 1], g[len - 1]);
        for (int i = 1; i < len; i++) {
            f[i] = g[i - 1] + nums[i];
            if (i != 1) g[i] = max(f[i - 1], g[i - 1]);
            else {
                g[i] = f[i - 1];
            }
        }
        ans2 = g[len - 1];
        return max(ans1, ans2);
    }
};

class Solution {
public:

    int hash[10100];

    int deleteAndEarn(vector<int>& nums) {
        int max_digit = 0;
        for (auto& e : nums) {
            hash[e] += e;
            max_digit = max(e, max_digit);
        }
        vector<int> f(max_digit + 1);
        vector<int> g(max_digit + 1);
        for (int i = 1; i <= max_digit; i++) {
            f[i] = g[i - 1] + hash[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[max_digit], g[max_digit]);
    }
};

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int m = costs.size();
        vector<int> x(m);
        vector<int> y(m);
        vector<int> z(m);
        x[0] = costs[0][0];
        y[0] = costs[0][1];
        z[0] = costs[0][2];
        for (int i = 1; i < m; i++) {
            x[i] = min(y[i - 1], z[i - 1]) + costs[i][0];
            y[i] = min(x[i - 1], z[i - 1]) + costs[i][1];
            z[i] = min(x[i - 1], y[i - 1]) + costs[i][2];
        }
        return min(min(x[m - 1], y[m - 1]), z[m - 1]);
    }
};

